package com.yq.leetcodeOld;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;

/**
 * @ClassName Solution20
 * @Description TODO
 * @Author yaoqiang
 * @Date 2022/3/22 9:14
 * @Version 1.0
 */
public class Solution20 {
    public static void main(String[] args) {
       String s="(){}[]" ;
      boolean res= isValid(s);
        System.out.println(res);
    }
    private static boolean isValid(String s) {
        int n = s.length();
        if (n % 2 == 1) {
            return false;
        }
        Deque<Character> stack = new LinkedList<>();
//        Map<Character,Character> map =new HashMap<>(){{
//            put(')','(');put(']','[');put('}','{');
//        }};
        HashMap<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put(']', '[');
        map.put('}', '{');

        for (char c : s.toCharArray()) {
            if (map.containsKey(c)) {
                if (stack.isEmpty() || stack.peek() != map.get(c)) {
                    return false;
                }
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }

    private static boolean isValid2(String s) {
        int n=s.length();
        if (n%2==1){return false;}
        Deque<Character> stack=new LinkedList<>();
        for (char c:s.toCharArray()){
            if (c=='('||c=='['||c=='{'){
                stack.push(c);
            }else {
                if (stack.isEmpty()){return false;}
                else if(c==')'&& stack.pop()!='('|| c==']'&& stack.pop()!='['|| c=='}'&& stack.pop()!='{'){
                   return false;
                }
            }
        }
        return stack.isEmpty();
    }

}
